package 回溯法;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author: yangwk
 * @date: 2023/3/30
 * @description:
 **/
public class 无向染色图问题 {
    static boolean[] visited = new boolean[1000];
    static List<List<Node>> result = new ArrayList<>();

    private static int count = 0;  // 记录颜色方案总数

    static class Node implements Cloneable {
        int val;
        int color;

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public int getColor() {
            return color;
        }

        public void setColor(int color) {
            this.color = color;
        }

        @Override
        protected Node clone() throws CloneNotSupportedException {
            return (Node) super.clone();
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", color=" + color +
                    '}';
        }
    }

    static class Edge implements Cloneable {
        Node from;
        Node to;

        public Node getFrom() {
            return from;
        }

        public void setFrom(Node from) {
            this.from = from;
        }

        public Node getTo() {
            return to;
        }

        public void setTo(Node to) {
            this.to = to;
        }

        @Override
        protected Edge clone() throws CloneNotSupportedException {
            return (Edge) super.clone();
        }
    }

    public static void main(String[] args) {
        int[][] arr = new int[][]{{0, 1}, {1, 2}, {0, 2}};
        Map<Integer, List<Node>> nodeMap = new HashMap<>();
        Map<Integer, Node> map = new HashMap<>();
        for (int[] ints : arr) {
            int anInt1 = ints[0];
            int anInt2 = ints[1];
            final Node node1 = new Node();
            node1.setVal(anInt1);
            final Node node2 = new Node();
            node2.setVal(anInt2);
            if (!map.containsKey(anInt1)) {
                map.put(anInt1, node1);
            }
            if (!map.containsKey(anInt2)) {
                map.put(anInt2, node2);
            }
            nodeMap.compute(anInt1, (integer, integers) -> {
                if (integers == null) {
                    integers = new ArrayList<>();
                }
                integers.add(node2);
                return integers;
            });
            nodeMap.compute(anInt2, (integer, integers) -> {
                if (integers == null) {
                    integers = new ArrayList<>();
                }
                integers.add(node1);
                return integers;
            });
        }
        find(nodeMap, map, 0, 3);
        System.out.println(result);
    }

    public static void find(Map<Integer, List<Node>> nodeMap, Map<Integer, Node> map, int currentNode, int total) {
        List<Node> collect1 = map.values().stream().map(e -> {
            try {
                return e.clone();
            } catch (CloneNotSupportedException ex) {
                ex.printStackTrace();
            }
            return null;
        }).collect(Collectors.toList());
        System.out.println(collect1);
        if (currentNode == total) {
            List<Node> collect = map.values().stream().map(e -> {
                try {
                    return e.clone();
                } catch (CloneNotSupportedException ex) {
                    ex.printStackTrace();
                }
                return null;
            }).collect(Collectors.toList());
            result.add(collect);
            return;
        }
        List<Node> adj = nodeMap.get(currentNode);
        Node node = map.get(currentNode);
        if (node.color == 0) {
            //黑
            node.color = 1;
            find(nodeMap, map, currentNode + 1, total);
            node.color = 2;
            if (adj != null) {
                for (Node next : adj) {
                    next.setColor(1);
                }
            }
            find(nodeMap, map, currentNode + 1, total);
            node.color = 0;
        } else {
            find(nodeMap, map, currentNode + 1, total);
        }

    }
}
